IOI 96 (Veszprem, Ungaria)
Problema 3 (Prelucrarea pieselor)

Se considera o linie de productie intr-o fabrica. Asupra unei piese trebuiesc
efectuate doua operatii: intai operatia "A", apoi operatia "B". Fiecare din
aceste operatii este efectuata de un anumit numar de masini. Figura 1 arata
organizarea liniei de productie, care lucreaza astfel: o masina de tip "A" ia
o piesa din magazia de intrare, realizeaza operatia "A" si pune piesa in
magazia intermediara. O masina de tip "B" ia o piesa din magazia intermediara,
realizeaza operatia "B" si pune piesa in magazia de iesire. Toate masinile
pot lucra in paralel si independent una de alta. Capacitatea fiecarei magazii
este nelimitata. Masinile au caracteristici diferite de performanta, fiecare
masina putand executa operatia respectiva intr-un timp propriu.
Scrieti un program care calculeaza timpul minim necesar pentru a realiza
operatia A asupra a N piese (subproblema A). Se considera ca activitatea
incepe la momentul 0.
Calculati de asemenea timpul minim necesar pentru a realiza ambele operatii
asupra celor N piese (subproblema B).

Intrare

Fisierul INPUT.TXT contine numere intregi pozitive pe cinci linii. Prima
linie contine N, numarul de piese (1<N<1000). Pe linia a doua este numarul
M1 masini de tip "A" (1<M1<30). Pe linia a treia sunt M1 numere intregi
reprezentand timpii de prelucrare proprii pentru fiecare masina de tip "A".
Liniile patru si cinci contin numarul M2 de masini de tip "B" (1<M2<30),
respectiv timpii de prelucrare pentru fiecare masina de tip "B". Timpul de
prelucrare al unei piese este masurat in unitati de timp si este format din
timpul necesar luarii unei piese dintr-o magazie, prelucrarea ei si depunerea
in alta magazie. Fiecare timp de prelucrare este cel putin 1 si cel mult 20

Iesire

Programul va scrie doua linii in fisierul OUTPUT.TXT. Prima linie contine un
numar intreg pozitiv: solutia subproblemei A. A doua linie contine solutia
subproblemei B.

Exemplu

Pentru fisierul INPUT.TXT:
5
2
1 1
3
3 1 4

fisierul OUTPUT.TXT va fi:
3
5
=========================================
Solutie (Mihai Stroe)

    Primul punct este extrem de simplu; pentru t incepind cu 1 si crescind
  cu 1 la fiecare pas, daca nu s-a ajuns la solutie, se calculeaza numarul
  maxim de piese care se pot executa pe prima grupa de masini in t unitati de
  timp. Ideea aceasta mi-a venit destul de tirziu, deoarece am cautat o rezol-
  vare constructiva, fara care nu se poate aborda punctul B. Rezolvarea
  constructiva consta in plasarea piesei i pe masina care o termina de
  executat cel mai repede, tinind cont de faptul ca, dupa ce s-au plasat
  piese, s-au modificat timpii de eliberare ai unor masini. Initial acestia
  sunt 0 pentru toate masinile; la trimiterea unei piese catre o masina libera
  creste timpul de eliberare al acesteia pentru a putea prelucra alte piese si
  se pastreaza timpul de terminare pentru operatia A, folosit apoi la punctul
  B. Ideea simpla am folosit-o doar spre final, pentru verificare.
    Punctul B este exponential; abordarea mea, euristica, a trecut sase din
  cele 10 teste, rezultatul fiind foarte aproape de cel corect si la celelalte
  patru. Rezolvarea foloseste ideea constructiva de la punctul A, cu
  modificarea urmatoare: o piesa intra in etapa B daca intilneste o masina
  libera si daca a fost executata etapa A. Din nou, piesa trebuie sa fie
  terminata cit mai repede.

type arr=array[1..1000]of longint;
     ar=array[1..30]of longint;
var x,na,nr,timp,nb,min,mp,i,j,k,l,m,n:longint;
    ta,tb,fa,fb:ar;
    fi,fo:text;
    to1,to2:arr;

procedure sort2(var v:ar;n:longint);
var i,j,min,mp:longint;
begin
  for i:=1 to n-1 do
      begin
        min:=0;
        for j:=i to n do
            if v[j]>min then begin min:=v[j];mp:=j;end;
        v[mp]:=v[i];
        v[i]:=min;
      end;
end;

procedure sort(var v:arr);
var i,j,min,mp:longint;
begin
  for i:=1 to n-1 do
      begin
        min:=9999;
        for j:=i to n do
            if v[j]<min then begin min:=v[j];mp:=j;end;
        v[mp]:=v[i];
        v[i]:=min;
      end;
end;

function max(i,j:longint):longint;
begin
  if i>j then max:=i else max:=j;
end;

begin
  assign(fi,'input.txt');
  reset(fi);
  readln(fi,n);
  readln(fi,na);
  for i:=1 to na do
      read(fi,ta[i]);
  readln(fi);
  readln(fi,nb);
  for i:=1 to nb do
      read(fi,tb[i]);
  readln(fi);
  close(fi);
  sort2(ta,na);
  sort2(tb,nb);

  for i:=1 to na do fa[i]:=0;
  for i:=1 to n do
      begin
        min:=9999;
        for j:=1 to na do
            if fa[j]+ta[j]<min then
               begin
                 min:=fa[j]+ta[j];
                 mp:=j;
               end;
        fa[mp]:=fa[mp]+ta[mp];
        to1[i]:=fa[mp];
      end;
  sort(to1);
  assign(fo,'output.txt');
  rewrite(fo);

  for i:=1 to nb do fb[i]:=0;
  for i:=1 to n do
      begin
        min:=9999;
        for j:=1 to nb do
            if max(fb[j],to1[i])+tb[j]<min then
               begin
                 min:=max(fb[j],to1[i])+tb[j];
                 mp:=j;
               end;
        fb[mp]:=max(fb[mp],to1[i])+tb[mp];
        to2[i]:=fb[mp];
      end;
  sort(to2);

  x:=to1[n];
  for timp:=1 to to1[n]-1 do
      begin
        nr:=0;
        for i:=1 to na do
            nr:=nr+(timp div ta[i]);
        if nr>=n then
           if timp<x then
              x:=timp;
      end;

  writeln(fo,x);
  writeln(fo,to2[n]);

  close(fo);
end.
------------------------------
